public class leetcode5_最长回文子串_中心扩展法 {
    public static void main(String[] args) {
        Solution16 solution16 = new Solution16();
        System.out.println(solution16.longestPalindrome("abad"));
    }
}

class Solution16 {
    public int expand(int l, int r, String s) {
        int left = l, right = r;
        while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
            right++;
            left--;
        }
//        System.out.printf("left %d, right %d , %d\n", left, right, right - left - 1);
        return right - left - 1;
    }
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) return "";
        if (s.length() == 1) return s;
        int left = 0, right = 0;
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            // 回文为奇数时
           int l1 = expand(i, i, s);

            // 回文为偶数时
           int l2 = expand(i, i+1, s);
           int len = Math.max(l1, l2);

           // 回文长度为奇数时
           if (len % 2 == 1) {
               left = i - len / 2;
               right = i + len / 2;
           } else { // 回文长度为偶数时
               left = i - (len - 1) / 2;
               right = i + (len - 1) / 2 + 1;
           }
           if (s.substring(left, right + 1).length() > ans.length()) {
               ans = s.substring(left, right + 1);
           }
        }
        return ans;
    }
}